import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution23 {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> priorityQueue=new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
        for (ListNode list : lists) {
            if (list!=null){
                priorityQueue.offer(list);
            }
        }
        ListNode first=new ListNode(-1,null);
        ListNode cur=first;
        while (!priorityQueue.isEmpty()){
            ListNode t=priorityQueue.poll();
            cur.next=t;
            cur=t;
            if (t.next!=null){
                priorityQueue.offer(t.next);
            }
        }
        return first.next;
    }

    public static void main(String[] args) {
        ListNode l1=new ListNode(1,new ListNode(4,new ListNode(5)));
        ListNode l2=new ListNode(1,new ListNode(3,new ListNode(4)));
        ListNode l3=new ListNode(2,new ListNode(6));
        System.out.println(new Solution23().mergeKLists(new ListNode[]{l1,l2,l3}).next.next.next.next.next.next.val);
    }
}
